Chromatic Number

定义 Definition

（图论）染色数：给一个图的每个顶点分配颜色，要求相邻顶点颜色不同时，所需的最少颜色数。常记为 **χ(G)**。在其他语境中也可字面理解为“色度数/色彩的数量”，但最常见用法是图论术语。

发音 Pronunciation (IPA)

/kroʊˈmætɪk ˈnʌmbər/

例句 Examples

The chromatic number of a triangle is three.
三角形图的染色数是 3。

Determining the chromatic number of a large graph can be computationally difficult, so researchers often use bounds and heuristics.
确定大型图的染色数在计算上可能很困难，因此研究者常用上界/下界与启发式方法来估计。

词源 Etymology

chromatic 来自希腊语 chroma（颜色），表示“与颜色有关的”；number 来自拉丁语 numerus（数字、数量）。在图论中，“coloring（染色）”是一种形象化说法：用“颜色”来表示不同类别，使相邻顶点不冲突；因此 chromatic number 就是“完成这种染色所需的最少颜色数”。

相关词 Related Words

• Graph
• Vertex
• Edge
• Coloring
• Chromatic Polynomial
• Clique
• Planar Graph
• Four Color Theorem
• Bipartite
• NP-Complete

文学与经典著作 Literary Works

• Introduction to Graph Theory（Douglas B. West）：在图着色章节中系统使用并讨论 chromatic number。
• Graph Theory（Reinhard Diestel）：以 χ(G) 为核心概念之一，贯穿图着色、结构性质与证明。
• Graph Theory（J. A. Bondy & U. S. R. Murty）：多处出现 chromatic number，并与团、平面图等主题关联。
• The Four-Color Theorem / Four Colours Suffice（Robin Wilson 等关于四色问题的著作）：围绕平面图染色与染色数的思想背景展开，常提到相关概念与记号。